# module 'poly' -- Polynômes

# Un polynôme est représenté par une liste de coefficients; ainsi, [1, 10, 5]
# représente le polynôme 1*X^0 + 10*X^1 + 5*X^2 (ou 1 + 10X + 5X^2). Il n'y a
# aucun moyen de supprimer les zéros "internes"; les zéros finaux sont retirés
# par la fonction normalize().

def normalize(p): # Retire les coefficients nuls non-nécessaires
	n = len(p)
	while p:
		if p[n-1]: return p[:n]
		n = n-1
	return []

def plus(a, b):
	if len(a) < len(b): a, b = b, a # on s'assure que deg(a) est le plus grand
	res = a[:] # on fait une copie
	for i in range(len(b)):
		res[i] = res[i] + b[i]
	return normalize(res)

def minus(a, b):
	if len(a) < len(b): a, b = b, a # on s'assure que deg(a) est le plus grand
	res = a[:] # on fait une copie
	for i in range(len(b)):
		res[i] = res[i] - b[i]
	return normalize(res)

def one(power, coeff): # Renvoie une représentation de coeff * X^power
	res = []
	for i in range(power): res.append(0)
	return res + [coeff]

def times(a, b):
	res = []
	for i in range(len(a)):
		for j in range(len(b)):
			res = plus(res, one(i+j, a[i]*b[j]))
	return res

def power(a, n): # Élève a à la puissance entière positive n
	if n = 0: return [1]
	if n = 1: return a
	if n/2*2 = n:
		b = power(a, n/2)
		return times(b, b)
	return times(power(a, n-1), a)

def der(a): # Première dérivée
	res = a[1:]
	for i in range(len(res)):
		res[i] = res[i] * (i+1)
	return res

# Pour calculer une primitive, on aurait besoin d'arithmétique rationnelle...
